#include <stdio.h>
#include <stdlib.h>

typedef struct Node *Ptr2Node;
struct Node
{
    int data;
    Ptr2Node next;
};
typedef Ptr2Node List;

void print_list(List L)
{
    Ptr2Node p = L;
    while (p != NULL)
    {
        printf("%d\n", p->data);
        p = p->next;
    }
}

Ptr2Node create_list_r(int A[], int N)
{
    Ptr2Node head, s, r;
    head = NULL; // s和r可以不用初始化为NULL，但head必须要
    for (int i = 0; i < N; i++)
    {
        s = (Ptr2Node) malloc(sizeof(struct Node));
        s->data = A[i];
        s->next = NULL;
        if (head == NULL)
        {
            head = r = s;
        }
        else
        {
            r->next = s;
            r = r->next;
        } 
    }
    return head;
}

Ptr2Node create_list_f(int A[], int N)
{
    Ptr2Node head, s;
    head = NULL;
    for (int i = 0; i < N; i++)
    {
        s = (Ptr2Node) malloc(sizeof(struct Node));
        s->data = A[i];
        s->next = NULL;
        if (head == NULL)
        {
            head = s;
        }
        else
        {
            s->next = head;
            head = s;
        }     
    }
    return head;
}

// 将新结点newVal插入到targetVal结点后面
void insert_node(List L, int targetVal, int newVal)
{
    printf("Let's insert a new element\n");
    Ptr2Node p = L;
    while (p && p->data != targetVal)
        p = p->next;
    if (p) {
        Ptr2Node s = (Ptr2Node) malloc(sizeof (struct Node));
        s->data = newVal;
        s->next = p->next;
        p->next = s;
    }
}

void delete_node(List *L, int targetVal)
{
    Ptr2Node prev, p;
    prev = NULL; // 概念上在开始之前，首结点的prev结点也应该指向NULL
    for (p = *L; p && p->data != targetVal; prev = p, p = p->next)
        ;

    if (!p) // 没找到该结点
        return;

    if (!prev) { // 删除的是第一个首结点
        *L = p->next;
    } else {
        prev->next = p->next;
    }
    free(p);
}

List reverse(List L)
{
    Ptr2Node Old_head, New_head, Temp;
    Old_head = L;
    New_head = NULL;
    while (Old_head != NULL)
    {
        Temp = Old_head->next;
        Old_head->next = New_head;
        New_head = Old_head;
        Old_head = Temp;
    }
    return New_head;
}

int main()
{
    int A[] = {100, 200, 300};
    Ptr2Node L = create_list_r(A, 3);
    print_list(L);

    insert_node(L, 100, 50);
    print_list(L);
    return 0;
}